题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

解答

使用对撞指针寻找一对左偶右奇的数进行交换。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l < r){ // 找一对左偶右奇的交换
            while(l < n && nums[l] % 2 == 1){ // 左指针为奇数
                l ++; // 不需要交换，直接下一个
            }
            while(r >= 0 && nums[r] % 2 == 0){ // 右指针为偶数
                r --; // 不需要交换，直接下一个
            }
            if(l >= r) return nums; // 没找到需要交换的，直接返回
            swap(nums[l], nums[r]); // 交换偶奇
        }
        return nums;
    }
};

复杂度

  • 时间复杂度 $O(N)$
  • 空间复杂度 $O(1)$